package com.mdnote.algorithm;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/7
 * @description KMP算法
 */
public class KmpAlgorithm {

    public static void main(String[] args) {

        KmpAlgorithm kmpAlgorithm = new KmpAlgorithm();
        int[] arr = kmpAlgorithm.getMatchingArray("BCD");
        System.out.println(Arrays.toString(arr));
//        int index = kmpAlgorithm.normalSearch("ABCDABC", "CD");
        int index = kmpAlgorithm.pmt("abcabcabcabcd", "abcd", arr);

        System.out.println(index);

    }

    /**
     * KMP搜索
     * @param str1 原字符串
     * @param str2 关键词
     * @param arr PMT
     * @return 索引
     */
    private int pmt(String str1, String str2, int[] arr) {

        for (int i = 0, j = 0; i < str1.length(); i++) {
            // i是str1的指针，j是str2的指针
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = arr[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * 获取匹配值
     * @param str 搜索词
     */
    private int[] getMatchingArray(String str) {
        int[] res = new int[str.length()];
        char[] arr = str.toCharArray();
        for (int j = 0, i = 1; i < arr.length; i++) {

            while (j > 0 && arr[i] != arr[j]) {
                j = res[j - 1];
            }
            // 处理重复的情况
            if (arr[i] == arr[j]) {
                j++;
            }
            res[i] = j;
        }
        return res;
    }

    /**
     * 普通匹配
     * @param str1 主串
     * @param str2 子串
     * @return 缩影
     */
    public int normalSearch(String str1, String str2) {

        for (int i = 0, j = 0; i < str1.length(); i++) {
            while (j < str2.length() && str1.charAt(i + j) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i;
            }
            j = 0;
        }
        return -1;
    }
}
